1. Field of the Invention
The present invention relates to an operation processing apparatus, an operation process control method, and a computer program. More specifically, the present invention relates to an operation processing apparatus using a logic circuit, an operation process control method, and a computer program, capable of efficiently performing an operation associated with common key cryptography such as that according to the AES (Advanced Encryption Standard) standard, or public key cryptography such as that according to the RSA (Rivest-Sharmir-Adleman) algorithm, or efficiently performing an operation associated with a hash function such as that according to SHA-1 (Secure Hash Algorithm 1).
2. Description of the Related Art
In recent years, network communication and electronic commerce have become very popular. As a result, security in communication is becoming increasingly important. One technique to achieve high security in communication is to use cryptography, and many cryptography techniques are actually used in communication.
Cryptography methods are categorized into two types: common key cryptography, and public key cryptography. Specific examples of common key cryptography techniques are that using a DES (Data Encryption Standard) algorithm and that using AES (Advanced Encryption Standard) algorithm. The AES cryptography is widely used as a successor to the DES cryptography. Specific examples of public key cryptography are RSA (Rivest-Shamir-Adleman) cryptography and ECC (Elliptic Curve Cryptography) cryptography.
A cryptographic processing device for performing a cryptographic process according to such an algorithm may be implemented on a CPU by executing a program written in a program language such as C, or may be implemented in the form of a hardware device using various gate circuits.
The cryptographic processing device performs a data encryption process to encrypt given plaintext into ciphertext or a data decryption process to decrypt given ciphertext into plaintext. It is desirable that the encryption or decryption process be performed in a secure manner so that information does not leak out. However, in reality, various techniques to analyze or attack keys or algorithms used in encryption or decryption are known. The attack methods can be categorized into two types, destructive attacks and nondestructive attacks.
In the destructive attack, a package of an IC chip is dissolved by a chemical process using a chemical agent such as nitric acid, and secret information is physically read from an exposed die of the IC chip. It is known to reproduce a circuit from an interconnection pattern on an exposed die. This is known as reverse engineering. It is possible to extract secret information directly from the interconnection pattern. It is also known to detect states of memory cells by irradiating the memory cells with a laser beam or an electromagnetic wave to observe secret information written in the memory.
The nondestructive attack is also called a side-channel attack. In this method, the package of the IC chip is not chemically resolved, but secret information is detected from physical information obtainable from the outside, such as a consumption current, electromagnetic radiation, operation time, etc. For example, in a paper written by Kocher et. al in 1999 (Paul C. Kocher, Joshaua Jaffe and Benjamin Jun, “Differential Power Analysis”, CRYPTO 1999, Lecture Note in Computer Science, Vol. 1666, Springer-Verlag (1999), pp. 388-397 (hereinafter, referred to as Non-Patent Document 1)), discussed is a technique to detect key information, which is secret information, by observing a change in consumption current which occurs when a cryptographic process according to a DES algorithm, which is one of common key cryptography techniques, is performed by a device. The presence of attack techniques results in a possibility that secret information leaks out unless secret, and thus there is a need for a technique to protect information more securely.
More specifically, in the DPA (Differential Power Analysis) attack discussed in Non-Patent Document 1, current consumption is observed for many cryptographic operations corresponding to different input plaintext, and the current consumption is statistically analyzed based on bit values of secret information. A current consumption pattern having a correlation with secret information is detected via the statistical analysis, and secret information is extracted from the current consumption pattern.
Various techniques to prevent secret information from the attacks described above have been proposed. For example, a technique to prevent information associated with AES algorithm, which is one of common key cryptography methods, is discussed in a paper by Elisabeth Oswald et al. (Elisabeth Oswald, Stefan Mangard, Norbert Pramstaller, “A Side-Channel Analysis Resistant Description of the AES S-box”, FSE 2005, LNCS 3557, pp. 413-423 (hereinafter, referred to as Non-Patent Document 2)). In this technique, an S-box operation called a subbyte transformation in the AES operation is protected by hiding intermediate values including secret information by using random numbers.
In a paper by Kris Tiri et al. (Kris Tiri, Ingrid Verbauwhede, “Securing Encryption Algorithms against DPA at the Logic Level: Next Generation Smart Card Technology”, CHES 2003, LNCS 2779, pp. 125-136 (hereinafter, referred to as Non-Patent Document 3)), a technique using WDDL (Wave Differential Dynamic Logic) is disclosed to protect secret information by performing an operation alternately in a pre-charge phase and an operation in an evaluation phase.
In the pre-charge phase, gate circuits are initialized, and an actual operation is performed in the evaluation phase. Inputs to the gate circuits are given in a complementary form, and outputs from the gate circuits appear in a complementary form. Positive logic and negative logic are formed for the complementary inputs thereby obtaining complementary outputs. In the WDDL technique in which the pre-charge phase and the evaluation phase are alternately performed and inputs and outputs appear in the complementary form, any signal is allowed to change only at a transition from the pre-charge phase to the evaluation phase or from the evaluation phase to the pre-charge phase.
Because of the above-described characteristic of the WDDL, unnecessary transient changes do not occur. Besides, in the WDDL, in response to any input, only one of two outputs changes. Thus no change occurs in current consumption of the CMOS (Complementary Metal Oxide Semiconductor) logic, because charging/discharging occurs only when a change occurs in the logic state. Therefore, a change in current consumption depending on the bit values of secret information does not occur. This is effective to protect secret information from the DPA attack.
The internal S-box operation called the subbyte transformation operation in the AES algorithm can be executed by hardware using, for example, a binary decision diagram (BDD). The binary decision diagram (BDD) will be described in detail later. The description of the binary decision diagram (BDD) may also be found, for example, in Japanese Unexamined Patent Application Publication No. 2003-223100 (hereinafter, referred to as Patent Document 1).
Patent Document 1 includes a discussion of a configuration of an S-box or a binary decision diagram (BDD) by a combinational circuit and a practical implementation thereof. The cryptographic operation using the common key cryptography includes a nonlinear conversion process using a nonlinear conversion unit called an S-box. The total operation speed of the cryptographic operation greatly depends on the operation speed of the S-box. For example, the S-box for the AES algorithm needs a circuit for determining inverse elements in a Galois field.
If this circuit is implemented using a composite field or the like instead of using a binary decision diagram (BDD), a circuit delay is a few times greater than that in the circuit based on the binary decision diagram (BDD). Thus, from the point of view of the operation speed, it is desirable to implement the circuit using the binary decision diagram (BDD).